﻿P2196[NOIP 1996 提高组] 挖地雷P2196[NOIP 1996 提高组] 挖地雷


题目描述
在一个地图上有 N(N≤20) 个地窖，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后每次可以移动到一个编号比当前节点大且联通的节点去挖地雷，当无满足条件的节点时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入格式
有若干行。

第 1 行只有一个数字，表示地窖的个数 N。

第 2 行有 N 个数，分别表示每个地窖中的地雷个数。

第 3 行至第 N + 1 行表示地窖之间的连接情况：

第 3 行有 n−1 个数（0 或 1），表示第一个地窖至第 2 个、第 3 个 … 第 n 个地窖有否路径连接。如第 3 行为 11000⋯0，则表示第 1 个地窖至第 2 个地窖有路径，至第 3 个地窖有路径，至第 4 个地窖、第 5 个 … 第 n 个地窖没有路径。

第 4 行有 n−2 个数，表示第二个地窖至第 3 个、第 4 个 … 第 n 个地窖有否路径连接。

……

第 n + 1 行有 1 个数，表示第 n−1 个地窖至第 n 个地窖有否路径连接。（为 0 表示没有路径，为 1 表示有路径）。

输出格式
第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。

第二行只有一个数，表示能挖到的最多地雷数。

输入输出样例
输入 #1复制
5
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1
输出 #1复制
1 3 4 5
27
说明 / 提示





//思路：dfs多叉遍历，边走边统计path与sum；到头就更新max_sum 与对应路径 

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const int N = 1e6 + 5;
bool vis[N];//进入dfs的时候已经来过的地窖 
vector<int>value;//地窖雷个数 
vector<vector<int>> edge;//地窖之间的可达边 
int n;
int ans = 0;//最后总地雷数 
vector<int> final_path;//最终路径 
vector<int>path; //dfs多叉遍历的时候可能出现的路径 
int final_step;//最后总步数 
//判断k位置的地窖是否还可以往其他地窖走： 
bool is_stop(int k) {
    int cnt = 0;
    for (int i = 1; i <= n; i++)	if (vis[i] || edge[k][i] == 0) cnt++;

    return cnt == n;
}
void dfs(int pos, int sum, int step) {

    if (is_stop(pos)) {
        //符合要求进行统计总的地雷个数以及路径 
        if (sum > ans) {
            ans = sum;
            final_step = step;
            for (int i = 1; i <= step; i++) final_path[i] = path[i];
            return;
        }
    }


    for (int i = 1; i <= n; i++) {
        //没来过+有路径： 
        if (!vis[i] && edge[pos][i] == 1) {
            vis[i] = 1;
            path[step + 1] = i;//记录走的第几步是i地窖 
            dfs(i, sum + value[i], step + 1);
            vis[i] = 0;
        }
    }
}


void dfs_solve() {

    cin >> n;
    value.resize(n + 1);
    //填充每个地窖地雷个数 ： 
    for (int i = 1; i <= n; i++) cin >> value[i];
    //地窖与地窖之间可达边（单向边）： 
    edge.resize(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++)	for (int j = i + 1; j <= n; j++) cin >> edge[i][j]; //注意单向边 
    //路径初始化： 
    path.resize(n + 1);
    final_path.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        vis[i] = 1;
        path[1] = i;//来到当前dfs i 里面已经走过了的地窖的数组 -->路径 
        dfs(i, value[i], 1);//假设dfs可以完成从i点之后的那些点的选择并更新完最终ans与path 
        vis[i] = 0;
    }


    for (int i = 1; i <= final_step; i++) cout << final_path[i] << " ";
    cout << endl << ans;

}

int main() {
    IOS;
    dfs_solve();


    return 0;
}



